 /*******************************************************************************
  * Copyright (c) 2004, 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.localstore;

 import java.io.*;
 import java.util.Arrays ;
 import java.util.Comparator ;
 import org.eclipse.core.internal.utils.UniversalUniqueIdentifier;
 import org.eclipse.core.runtime.IPath;

 public class HistoryBucket extends Bucket {

     /**
      * A entry in the bucket index. Each entry has one path and a collection
      * of states, which by their turn contain a (UUID, timestamp) pair.
      * <p>
      * This class is intended as a lightweight way of hiding the internal data structure.
      * Objects of this class are supposed to be short-lived. No instances
      * of this class are kept stored anywhere. The real stuff (the internal data structure)
      * is.
      * </p>
      */
     public static final class HistoryEntry extends Bucket.Entry {

         final static Comparator COMPARATOR = new Comparator () {
             public int compare(Object o1, Object o2) {
                 byte[] state1 = (byte[]) o1;
                 byte[] state2 = (byte[]) o2;
                 return compareStates(state1, state2);
             }
         };

         // the length of each component of the data array
 private final static byte[][] EMPTY_DATA = new byte[0][];
         // the length of a long in bytes
 private final static int LONG_LENGTH = 8;
         // the length of a UUID in bytes
 private final static int UUID_LENGTH = UniversalUniqueIdentifier.BYTES_SIZE;
         public final static int DATA_LENGTH = UUID_LENGTH + LONG_LENGTH;

         /**
          * The history states. The first array dimension is the number of states. The
          * second dimension is an encoding of the {UUID,timestamp} pair for that entry.
          */
         private byte[][] data;

         /**
          * Comparison logic for states in byte[] form.
          *
          * @see Comparator#compare(java.lang.Object, java.lang.Object)
          */
         private static int compareStates(byte[] state1, byte[] state2) {
             long timestamp1 = getTimestamp(state1);
             long timestamp2 = getTimestamp(state2);
             if (timestamp1 == timestamp2)
                 return -UniversalUniqueIdentifier.compareTime(state1, state2);
             return timestamp1 < timestamp2 ? +1 : -1;
         }

         /**
          * Returns the byte array representation of a (UUID, timestamp) pair.
          */
         private static byte[] getState(UniversalUniqueIdentifier uuid, long timestamp) {
             byte[] uuidBytes = uuid.toBytes();
             byte[] state = new byte[DATA_LENGTH];
             System.arraycopy(uuidBytes, 0, state, 0, uuidBytes.length);
             for (int j = 0; j < LONG_LENGTH; j++) {
                 state[UUID_LENGTH + j] = (byte) (0xFF & timestamp);
                 timestamp >>>= 8;
             }
             return state;
         }

         private static long getTimestamp(byte[] state) {
             long timestamp = 0;
             for (int j = 0; j < LONG_LENGTH; j++)
                 timestamp += (state[UUID_LENGTH + j] & 0xFFL) << j * 8;
             return timestamp;
         }

         /**
          * Inserts the given item into the given array at the right position.
          * Returns the resulting array. Returns null if the item already exists.
          */
         private static byte[][] insert(byte[][] existing, byte[] toAdd) {
             // look for the right spot where to insert the new guy
 int index = search(existing, toAdd);
             if (index >= 0)
                 // already there - nothing else to be done
 return null;
             // not found - insert
 int insertPosition = -index - 1;
             byte[][] newValue = new byte[existing.length + 1][];
             if (insertPosition > 0)
                 System.arraycopy(existing, 0, newValue, 0, insertPosition);
             newValue[insertPosition] = toAdd;
             if (insertPosition < existing.length)
                 System.arraycopy(existing, insertPosition, newValue, insertPosition + 1, existing.length - insertPosition);
             return newValue;
         }

         /**
          * Merges two entries (are always sorted). Duplicates are discarded.
          */
         private static byte[][] merge(byte[][] base, byte[][] additions) {
             int additionPointer = 0;
             int basePointer = 0;
             int added = 0;
             byte[][] result = new byte[base.length + additions.length][];
             while (basePointer < base.length && additionPointer < additions.length) {
                 int comparison = compareStates(base[basePointer], additions[additionPointer]);
                 if (comparison == 0) {
                     result[added++] = base[basePointer++];
                     // duplicate, ignore
 additionPointer++;
                 } else if (comparison < 0)
                     result[added++] = base[basePointer++];
                 else
                     result[added++] = additions[additionPointer++];
             }
             // copy the remaining states from either additions or base arrays
 byte[][] remaining = basePointer == base.length ? additions : base;
             int remainingPointer = basePointer == base.length ? additionPointer : basePointer;
             int remainingCount = remaining.length - remainingPointer;
             System.arraycopy(remaining, remainingPointer, result, added, remainingCount);
             added += remainingCount;
             if (added == base.length + additions.length)
                 // no collisions
 return result;
             // there were collisions, need to compact
 byte[][] finalResult = new byte[added][];
             System.arraycopy(result, 0, finalResult, 0, finalResult.length);
             return finalResult;
         }

         private static int search(byte[][] existing, byte[] element) {
             return Arrays.binarySearch(existing, element, COMPARATOR);
         }

         public HistoryEntry(IPath path, byte[][] data) {
             super(path);
             this.data = data;
         }

         public HistoryEntry(IPath path, HistoryEntry base) {
             super(path);
             this.data = new byte[base.data.length][];
             System.arraycopy(base.data, 0, this.data, 0, this.data.length);
         }

         /**
          * Compacts the data array removing any null slots. If non-null slots
          * are found, the entry is marked for removal.
          */
         private void compact() {
             if (!isDirty())
                 return;
             int occurrences = 0;
             for (int i = 0; i < data.length; i++)
                 if (data[i] != null)
                     data[occurrences++] = data[i];
             if (occurrences == data.length)
                 // no states deleted
 return;
             if (occurrences == 0) {
                 // no states remaining
 data = EMPTY_DATA;
                 delete();
                 return;
             }
             byte[][] result = new byte[occurrences][];
             System.arraycopy(data, 0, result, 0, occurrences);
             data = result;
         }

         public void deleteOccurrence(int i) {
             markDirty();
             data[i] = null;
         }

         byte[][] getData() {
             return data;
         }

         public int getOccurrences() {
             return data.length;
         }

         public long getTimestamp(int i) {
             return getTimestamp(data[i]);
         }

         public UniversalUniqueIdentifier getUUID(int i) {
             return new UniversalUniqueIdentifier(data[i]);
         }

         public Object getValue() {
             return data;
         }

         public boolean isEmpty() {
             return data.length == 0;
         }

         public void visited() {
             compact();
         }

     }

     /**
      * Version number for the current implementation file's format.
      * <p>
      * Version 2 (3.1 M5):
      * <pre>
      * FILE ::= VERSION_ID ENTRY+
      * ENTRY ::= PATH STATE_COUNT STATE+
      * PATH ::= string (does not include project name)
      * STATE_COUNT ::= int
      * STATE ::= UUID LAST_MODIFIED
      * UUID ::= byte[16]
      * LAST_MODIFIED ::= byte[8]
      * </pre>
      * </p>
      * <p>
      * Version 1 (3.1 M4):
      * <pre>
      * FILE ::= VERSION_ID ENTRY+
      * ENTRY ::= PATH STATE_COUNT STATE+
      * PATH ::= string
      * STATE_COUNT ::= int
      * STATE ::= UUID LAST_MODIFIED
      * UUID ::= byte[16]
      * LAST_MODIFIED ::= byte[8]
      * </pre>
      * </p>
      */
     public final static byte VERSION = 2;

     public HistoryBucket() {
         super();
     }

     public void addBlob(IPath path, UniversalUniqueIdentifier uuid, long lastModified) {
         byte[] state = HistoryEntry.getState(uuid, lastModified);
         String pathAsString = path.toString();
         byte[][] existing = (byte[][]) getEntryValue(pathAsString);
         if (existing == null) {
             setEntryValue(pathAsString, new byte[][] {state});
             return;
         }
         byte[][] newValue = HistoryEntry.insert(existing, state);
         if (newValue == null)
             return;
         setEntryValue(pathAsString, newValue);
     }

     public void addBlobs(HistoryEntry fileEntry) {
         IPath path = fileEntry.getPath();
         byte[][] additions = fileEntry.getData();
         String pathAsString = path.toString();
         byte[][] existing = (byte[][]) getEntryValue(pathAsString);
         if (existing == null) {
             setEntryValue(pathAsString, additions);
             return;
         }
         setEntryValue(pathAsString, HistoryEntry.merge(existing, additions));
     }

     protected Bucket.Entry createEntry(IPath path, Object value) {
         return new HistoryEntry(path, (byte[][]) value);
     }

     public HistoryEntry getEntry(IPath path) {
         String pathAsString = path.toString();
         byte[][] existing = (byte[][]) getEntryValue(pathAsString);
         if (existing == null)
             return null;
         return new HistoryEntry(path, existing);
     }

     protected String getIndexFileName() {
         return "history.index"; //$NON-NLS-1$
 }
     
     protected byte getVersion() {
         return VERSION;
     }

     protected String getVersionFileName() {
         return "history.version"; //$NON-NLS-1$
 }

     protected Object readEntryValue(DataInputStream source) throws IOException {
         int length = source.readUnsignedShort();
         byte[][] uuids = new byte[length][HistoryEntry.DATA_LENGTH];
         for (int j = 0; j < uuids.length; j++)
             source.read(uuids[j]);
         return uuids;
     }

     protected void writeEntryValue(DataOutputStream destination, Object entryValue) throws IOException {
         byte[][] uuids = (byte[][]) entryValue;
         destination.writeShort(uuids.length);
         for (int j = 0; j < uuids.length; j++)
             destination.write(uuids[j]);
     }
 }

